/**
 * @author Akos Szabo - Axi - aaszabo@gmail.com
 * Dec 12, 2011
 * 
 * Implements all com.axi.ga.GaEngine required components.
 * This runs the GA for finding the proper schedule of tasks.
 */

package com.axi.resplan;

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Random;
import java.util.Vector;

import com.axi.ga.IDns;
import com.axi.ga.IDnsHandler;
import com.axi.ga.IGaListener;
import com.axi.util.VectorCutable;


public class ResPlanGa implements IDnsHandler, IGaListener
{

	private static int AUX_CNT = 0;
	
	private VectorCutable _population;
	
	private int _populationSize=0;
	
	TimeTable _tt;
	
	IDns _theBest = null;
	
	/** for storing the result of evaluation for the BEST dns*/
	Hashtable _bestHt;
	
	private Hashtable _ht;
	
	/**
	 * Constructor
	 * @param argTimeTable
	 */
	public ResPlanGa( TimeTable argTimeTable)
	{
		_tt = argTimeTable;
	}
	
	//INTERFACE methods - IGaListener
	
	/* (non-Javadoc)
	 * @see com.axi.ga.IGaListener#terminated(com.axi.ga.IDns)
	 */
	@Override
	public void terminated(IDns argTheBest)
	{
		// TODO Auto-generated method stub

	}

	/* (non-Javadoc)
	 * @see com.axi.ga.IGaListener#meetTheRequirement(com.axi.ga.IDns)
	 */
	@Override
	public void meetTheRequirement(IDns argTheBest) 
	{
		// TODO Auto-generated method stub

	}

	/* (non-Javadoc)
	 * @see com.axi.ga.IGaListener#cycleEnd(com.axi.ga.IDns)
	 */
	@Override
	public void cycleEnd(IDns argTheBest) 
	{
		// TODO Auto-generated method stub

	}

	/* (non-Javadoc)
	 * @see com.axi.ga.IGaListener#lifeStopped(com.axi.ga.IDns)
	 */
	@Override
	public void lifeStopped(IDns argTheBest) 
	{
		// TODO Auto-generated method stub

	}

	/* (non-Javadoc)
	 * @see com.axi.ga.IGaListener#lifeStarted()
	 */
	@Override
	public void lifeStarted() 
	{
		System.out.println("ResPlanGa > lifeStarted");
		// TODO Auto-generated method stub

	}

	
	//INTERFACE methods - IDnsHandler methods
	
	/* (non-Javadoc)
	 * @see com.axi.ga.IDnsHandler#originatePopulation(int)
	 */
	@Override
	public Vector originatePopulation(int argPopulationSize) 
	{
		// TODO Auto-generated method stub
		_populationSize = argPopulationSize;
		_population = new VectorCutable(_populationSize);
		
		for(int i=0; i<_populationSize; i++)
			_population.add(createDns());
		
		sortPopulation();		
		
		
		return _population;
	}

	/**
	 * This creates new entities.
	 * The process is to get entities more probably the betters and cross them
	 * 
	 *  Selection is a roulette selection where the worst has one position on the roulet wheel and each has as many as its position in the sorted list.
	 *  It creates as many new entities as many the half of the population
	 *  
	 *  Cross over is a simple cross. At a randomly selected position the rest of the dns are flipped
	 * 
	 * @see com.axi.ga.IDnsHandler#crossOverPopulation()
	 */
	@Override
	public IDns crossOverPopulation() 
	{
		// select pairs and cross over them
		int popMaxIndex = _population.size()-1;
		
		int maxi = popMaxIndex/2;
		int ind1, ind2;
		Random rndN = new Random();
		int maxRnd = (popMaxIndex*popMaxIndex+popMaxIndex)/2;
		for(int i=0; i<maxi; i++)
		{
			ind1=rndN.nextInt(maxRnd);
			ind1= (int)(( Math.sqrt( (double)(8*ind1+1) ) - 1 ) / 2);
			ind2=rndN.nextInt(maxRnd);
			ind2= (int)(( Math.sqrt( (double)(8*ind2+1) ) - 1 ) / 2);
			
			IDns d1 = (IDns)_population.get(ind1);
			IDns d2 = (IDns)_population.get(ind2);

			//crossover parents to get a new Dns
			//evaluate newborn
			IDns newDns = crossover(d1,d2);
			//add newborns to the population
			_population.add(newDns);
			//System.arraycopy(elementData, index+1, elementData, index, numMoved);
			
			
		}

		//sort the population
		sortPopulation();
		
		//cut the population
		_population.cutLeft(popMaxIndex+1);
		
		//return the best
		return _theBest;
	}

	
		
	/* (non-Javadoc)
	 * @see com.axi.ga.IDnsHandler#getTheBest()
	 * The best is set at the end of a life cycle sort
	 */
	@Override
	public IDns getTheBest() 
	{
		return _theBest;
	}


	//Own methods
	
	private IDns createDns()
	{
		ResPlanDns d = new ResPlanDns(_tt);
		evaluateDns(d);
		return d;
	}
	
	
	
	/**
	 * Crosses parents to give birth to a child
	 * @param argDns1
	 * @param argDns2
	 * @return
	 */
	public IDns crossover(IDns argDns1, IDns argDns2)
	{
		ResPlanDns parentA = (ResPlanDns)argDns1;
		ResPlanDns parentB = (ResPlanDns)argDns2;
		
		Random rndN = new Random();
		int l = rndN.nextInt(parentA._dns.length());
		String resStr =  parentA._dns.substring(0, l) + parentB._dns.substring(l);
				
		ResPlanDns child = new ResPlanDns();
		child._tt = this._tt;
		child._dns = resStr;
		evaluateDns(child);
		
		return child;		
	}
	
	
	/**
	 * Calculates the fitness value for a Dns
	 * @param argDns
	 */
	public void evaluateDns( IDns argDns )
	{
		
		ResPlanDns d = (ResPlanDns) argDns;
		//készíts annyi vektort ahány erőforrás van. Ezt késöbb lehet majd gyorsítani
		
				//fuss annyiszor ahány task van
					//vedd a következő DNS-t, ami a következő feladathoz a sorban mondja meg, hogy kihez tartozik és neki hanyadik a sorban
						//darabold fel 
						//első rész alapján modulus segítségével válaszd ki a vektort
						//második rész segítségével szúrd be a helyére
				
				//Az előállt vektorok alapján nézd meg az időzítést
				//jóságot befolyásoló tényezők
				//mennyi százaléka lóg ki a megoldásnak az adott térből
				//mennyire inhomogén az eloszlás - elvileg az a jó, ha van olyan erőforrás, akire nem jut, vagy csak kevés feladat
				

				//egyelőre véletlenszám generátor kicsit megvezetve.
				//minél többet kérdezik le annál nagyobbat mondhat
				//Random rndR = new Random();
				//d._fitness = rndR.nextInt(1000 + AUX_CNT++);
				
				
				
		Vector resV = _tt.getResourceVector();
		int resNumMax = resV.size();
		Vector taskV = _tt.getTaskVector();
		int[] workTimeList = new int[resNumMax];
		//Create a list of vectors where a vector belongs to a resource
		//processing a dns the method puts a task to the vector belongs to the resource given by the dns
		//dns gives an index for task order. Task must be inserted into the vector to assure the orders of dns
		
		_ht = new Hashtable();
		Enumeration en = resV.elements();
		while(en.hasMoreElements())
		{
			String resName = (String)en.nextElement();
			_ht.put(resName, new TaskVector());
		}
		
		
		//fill the cells according to the _dns which should be the best from GA population
		//HOGY nézzen ki a DNS???
		//egy string 
		//szakaszkból áll
		//a szakaszok feladatoknak felelnek meg
		//az első szakasz az első feladaté, a második a másodiké és így tovább
		//egy szakasz leírja, hogy kinek a feladata és annak az erőforrásnak ez hanyadik feladata
		//A feladat tulajdonosát egy (esetleg 2) byte azonosítja. A szám adja meg, hogy melyik erőforrásé a feladat:
		// szam%rscNum, vagyis a szám maradékos osztása határozza meg.
		//a sorrendet két byte-on írja le egy számláló.
		//a sorrend nem zárt sorszámozású. A nagyobb szám jön késöbb.
		String dnsStr = argDns.toString();
		int maxi = dnsStr.length();
		int resNum, orderNum;		 
		for(int i = 0, j=0; i<maxi; i+=16, j++)//16 because the two byte gene size
		{
			String gene = dnsStr.substring(i, i+16);
			
			//culate resnum with max res num			
			resNum = Integer.parseInt(gene.substring(0,8), 2);
			resNum = resNum % resNumMax;
			
			
			orderNum = Integer.parseInt(gene.substring(8,16), 2);
			
			//could write info back to Task stored in TimeTable
			Task t = (Task)taskV.elementAt(j);
			t.setIndex(orderNum);
			String resName = (String)resV.elementAt(resNum);
			t.setOwner(resName);
			//Line below works till in evaluation a new TaskVector is created for DNS evaluations
			TaskVector tv = (TaskVector)_ht.get( resName );
			tv.insertTaskIntoVector(t);
			workTimeList[resNum]+=t._lengthInHour;
		}

		
		//by this point the hashtable contains all the tasks in the hashtable passed to resources by keys
		//vectors passed to resources by keys contains tasks in the processing order
		//workTimeList[resNumMax] tells the worktime for each resource
		int minWork=Integer.MAX_VALUE, maxWork=Integer.MIN_VALUE;
		int totalWorkTime=0;
		for(int i=0; i<resNumMax;i++)
		{
			if( workTimeList[i]>maxWork )
				maxWork = workTimeList[i];
			
			if( workTimeList[i]<minWork )
				minWork = workTimeList[i];
			
			totalWorkTime += workTimeList[i];
		}

		d._fitness = 100000 - maxWork;		
	}//end of evaluation
	
	
	
	/**
	 * Sort the population elements and treat well the best by saving it.
	 * Save a clone not just a reference for possible further processes.
	 */
	private void sortPopulation()
	{
		System.out.println("ResPlanGa > sortPopulation START");
		Enumeration en = _population.elements();
		int i=0;
		while(en.hasMoreElements())
		{
			ResPlanDns rpd = (ResPlanDns)en.nextElement();
			System.out.print("["+i+":"+rpd.getFitness()+"]");
			i++;
		}
		
		//the only usefull command in this method
		quickSort(_population, 0, _population.size()-1);		
		saveTheBest();
		
		
		//just for display the result of sort		
		System.out.println("");
		en = _population.elements();
		i=0;
		while(en.hasMoreElements())
		{
			ResPlanDns rpd = (ResPlanDns)en.nextElement();
			System.out.print("["+i+":"+rpd.getFitness()+"]");
			i++;
		}
		System.out.println("");
		
		System.out.println("ResPlanGa > sortPopulation END");
	}
	
	
	
	/**
	 * Sort elements in the Vector between the given indexes
	 * @param argV
	 * @param left
	 * @param right
	 */
	private void quickSort(Vector argV, int left, int right) 
	{
		//System.out.println("ResPlanGa > quickSort START");
		if(right > left) 
		{
			ResPlanDns o1 = (ResPlanDns)argV.elementAt(right);
			int i = left - 1;
			int j = right;
			while(true) 
			{
				while( ((ResPlanDns)argV.elementAt(++i))._fitness < o1._fitness);
	        
				while(j > 0)
					//if(compare.lessThanOrEqual(argV.elementAt(--j), o1)) break; // out of while
					if( ((ResPlanDns)argV.elementAt(--j))._fitness <= o1._fitness) break; // out of while
				
				if(i >= j) break;
				
				swap(argV, i, j);
			}
			swap(argV, i , right);
			quickSort(argV, left, i-1);
			quickSort(argV, i+1, right);
	    }
	  }//end of quickshort
	
	
	/**
	 * Swap two elements specified with indexes in the given Vector
	 * This is used for the quick sort algorithm mainly
	 * @param argV
	 * @param arg1
	 * @param arg2
	 */
	private void swap(Vector argV, int arg1, int arg2)
	{
		Object S = argV.elementAt(arg1);
		argV.set( arg1, argV.elementAt(arg2) );
		argV.set(arg2, S);
	}
	
	
	
/*	
	public void quickSort_old(Vector argV,int low, int n)
	{
		System.out.println("ResPlanGa > quickSort");
		int lo = low;
		int hi = n;
	  if (lo >= n) 
	  {
		 return;
	  }
	  
	  int mid = ((ResPlanDns)(argV.get((lo + hi) / 2)))._fitness;
	  while (lo < hi) 
	  {
		  while (lo<hi && ((ResPlanDns)(argV.get(lo)))._fitness < mid) 
		  {
			  lo++;
		  }
		  while (lo<hi && ((ResPlanDns)(argV.get(hi)))._fitness > mid) 
		  {
			  hi--;
		  }

		  //Need to swap?
		  if (lo < hi) 
		  {
			  Object T = argV.get(lo);//array[lo];
			  argV.set(lo, argV.get(hi)); //array[lo] = array[hi];
			  argV.set(hi,T); // array[hi] = T;
		  }
	  }
	  
	  if (hi < lo) 
	  {
		  int T = hi;
		  hi = lo;
		  lo = T;
	  }
	  
	  quickSort(argV, low, lo);
	  quickSort(argV, lo == low ? lo+1 : lo, n);
	  
	}//end of quicsort
*/
	

	/**
	 * This is for saving the result of the evaluation of _theBest IDns from the _population.
	 * It must be run at the end of the sortPopulation method
	 */
	private void saveTheBest()
	{
		_theBest = (IDns)_population.lastElement();
		evaluateDns(_theBest);
		_bestHt = new Hashtable();
				
		//clone the hashtable of the evaluation of the best
		Enumeration en = _ht.keys();
		while(en.hasMoreElements())
		{
			String key = (String)en.nextElement();
			TaskVector tv = (TaskVector)_ht.get(key);
			TaskVector v = tv.clone();
			_bestHt.put(key, v);
		}
	}
	
	
	/**
	 * Returns the processed content of the best DNS
	 * @return
	 */
	public Hashtable getTheBestDetails()
	{
		return _bestHt;
	}
}
